package io.lvdaxian.leetcode.str.and.array;

import io.lvdaxian.common.CommonUtils;
import org.junit.Test;

/**
 * 给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素。元素的顺序可能发生改变。然后返回 nums 中与 val 不同的元素的数量。
 * <p>
 * 假设 nums 中不等于 val 的元素数量为 k，要通过此题，您需要执行以下操作：
 * <p>
 * 更改 nums 数组，使 nums 的前 k 个元素包含不等于 val 的元素。nums 的其余元素和 nums 的大小并不重要。
 * 返回 k。
 * <a href="https://leetcode.cn/problems/remove-element/description/?envType=study-plan-v2&envId=top-interview-150">...</a>
 *
 * @author lihh
 */
public class L27_RemoveElement_Case001 {
  
  @Test
  public void testCase001() {
    int[] nums = new int[]{3, 2, 2, 3};
    
    int k = removeElement(nums, 2);
    System.out.printf("case001 相同元素个数是: %s%n", k);
    System.out.printf("case001 数组内容是: %s%n", CommonUtils.printArray(nums));
  }
  
  @Test
  public void testCase002() {
    int[] nums = new int[]{2};
    
    int k = removeElement(nums, 2);
    System.out.printf("case002 相同元素个数是: %s%n", k);
    System.out.printf("case002 数组内容是: %s%n", CommonUtils.printArray(nums));
  }
  
  @Test
  public void testCase003() {
    int[] nums = new int[]{0, 1, 2, 2, 3, 0, 4, 2};
    
    int k = removeElement(nums, 2);
    System.out.printf("case003 相同元素个数是: %s%n", k);
    System.out.printf("case003 数组内容是: %s%n", CommonUtils.printArray(nums));
  }
  
  @Test
  public void testCase004() {
    int[] nums = new int[]{1};
    
    int k = removeElement(nums, 1);
    System.out.printf("case004 相同元素个数是: %s%n", k);
    System.out.printf("case004 数组内容是: %s%n", CommonUtils.printArray(nums));
  }
  
  private void wrap(int[] nums, int l, int r) {
    int tmp = nums[l] ^ nums[r];
    nums[l] = tmp ^ nums[l];
    nums[r] = tmp ^ nums[r];
  }
  
  public int removeElement(int[] nums, int val) {
    // 表示相同元素个数
    int k = 0, endIdx = nums.length - 1;
    
    // 这是 O(n) 的操作
    for (int idx = 0; idx < nums.length && endIdx >= 0 && idx <= endIdx; ) {
      int current = nums[idx];
      
      // 如果不相同的话 不予理会
      if (current != val) {
        idx += 1;
        ++k;
        continue;
      }
      
      // 替换前进行判断 eg：不能将2 v 2进行替换
      while (endIdx >= 0 && val == nums[endIdx]) {
        wrap(nums, endIdx, endIdx--);
      }
      
      // 将相同的元素 替换掉
      if (endIdx >= 0 && idx <= endIdx) {
        wrap(nums, idx, endIdx--);
      }
    }
    
    return k;
  }
}
